import java.util.Arrays;

public class Test {
}
class Solution {
    //dfs(row,col,prev) = dfs(row-1,col,prev)+grid[row][col]
    //grid[r][c] = grid[r-1][c1]+grid[r][c]
    public int minFallingPathSum(int[][] grid) {
        int n = grid.length;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = Integer.MAX_VALUE;
                d[0][j] = grid[0][j];
            }
        }
        for(int i=1; i<grid.length; i++){
            for(int j=0; j<grid.length; j++){
                for(int k=0; k<grid.length; k++){
                    if(k != j){
                        d[i][j] = Math.min(d[i][j],d[i-1][k] + grid[i][j]);
                    }
                }
            }
        }
        Arrays.sort(d[grid.length-1]);
        return d[grid.length-1][0];
    }
}
class Solution2 {
    public int maxProfit(int[] prices) {
        int res = 0;
        for(int i=1; i<prices.length; i++){
            int ret = prices[i]-prices[i-1];
            if(ret > 0){
                res += ret;
            }
        }
        return res;
    }
}

class Solution3 {
    public boolean canJump(int[] nums) {
        int max = 0;
        for(int i=0; i<nums.length; i++){
            if(i <= max){
                max = Math.max(max,i+nums[i]);
            }else{
                return false;
            }
        }
        return true;
    }
}
class Solution4 {
    public int jump(int[] nums) {
        int ret = 0;int count = 0;
        if(nums.length==1) return 0;
        for(int i=0; i<=ret; i++){
            int tmp = ret;
            while(i<=tmp){
                ret = Math.max(ret, i+nums[i]);
                i++;
            }
            i--;
            count++;
            if(ret >= nums.length-1)
                return count;
        }
        return 0;
    }
}